#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int f[N];
int v[N], w[N];
int n, m;
int main()
{
    cin >> n >> m;
    for (int i = 1;i <= n;i++)
    {
        cin >> v[i]>> w[i];
    }
    //背包
//     for (int i = 1;i <= n;i++)
//     {
//         for (int j = 0;j <= m;j++)//j要从0开始
//         {
//             //状态表示为从前I个物品价值挑选出体积不超过j的最大价值
//             //必须有的是我不选当前这一个
//             f[i][j] = f[i - 1][j];
//             if (j >= v[i])
//             {
//                 //如果当前体积小于规定的最大体积
//                 f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
//             }
//         }
//     }
//     cout << f[n][m] << endl;
//     memset(f, -0x3f, sizeof(f));//因为memset是对于每个字节进行操作所以每个字节-0x3f实际上很小了
//     f[0][0] = 0;
//     for (int i = 1;i <= n;i++)
//     {
//         for (int j = 0;j <= m;j++)
//         {
//             //当价值为0但是最大承重不等于0的时候是不满的
//             //实际上有很多位置都不是满的。
//             //我们把所有的不是满的的地方都初始化为负无穷，只要去值相加取到了负无穷，说明这个地方就是不合法的
//             //只需要判断一下最后一个地方是不是小于0就可以判断是否能取满
//             f[i][j] = f[i - 1][j];
//             if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
//         }
//     }
//     if (f[n][m] < 0) cout << 0 << endl;
//     else cout << f[n][m] << endl;
    
    //空间优化版本  去一维并且让j从后往前遍历
    for (int i = 1;i <= n;i++)
    {
        for (int j = m;j >=0;j--)//j要从0开始
        {
            //状态表示为从前I个物品价值挑选出体积不超过j的最大价值
            //必须有的是我不选当前这一个
            //f[j] =[j];
            if (j >= v[i])
            {
                //如果当前体积小于规定的最大体积
                f[j] = max(f[j], f[j - v[i]] + w[i]);
            }
        }
    }
    cout << f[m] << endl;
    memset(f, -0x3f, sizeof(f));//因为memset是对于每个字节进行操作所以每个字节-0x3f实际上很小了
    f[0] = 0;
    for (int i = 1;i <= n;i++)
    {
        for (int j = m;j >=0;j--)
        {
            //当价值为0但是最大承重不等于0的时候是不满的
            //实际上有很多位置都不是满的。
            //我们把所有的不是满的的地方都初始化为负无穷，只要去值相加取到了负无穷，说明这个地方就是不合法的
            //只需要判断一下最后一个地方是不是小于0就可以判断是否能取满
            //f[j] = f[j];
            if (j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    if (f[m] < 0) cout << 0 << endl;
    else cout << f[m] << endl;
    return 0;
}